/**
 * 450. 删除二叉搜索树中的节点
 *
 * 【中等】
 *
 * 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
 * 一般来说，删除节点可分为两个步骤：
 * 1. 首先找到需要删除的节点；
 * 2. 如果找到了，删除它。
 *
 * 示例 1:
 * https://assets.leetcode.com/uploads/2020/09/04/del_node_1.jpg
 * 输入：root = [5,3,6,2,4,null,7], key = 3
 * 输出：[5,4,6,2,null,null,7]
 * 解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
 * 一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
 * 另一个正确答案是 [5,2,6,null,4,null,7]。
 * https://assets.leetcode.com/uploads/2020/09/04/del_node_supp.jpg
 *
 * 示例 2:
 * 输入: root = [5,3,6,2,4,null,7], key = 0
 * 输出: [5,3,6,2,4,null,7]
 * 解释: 二叉树不包含值为 0 的节点
 *
 * 示例 3:
 * 输入: root = [], key = 0
 * 输出: []
 */

import { TreeNode } from '../utils/tree'

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
	if (!root) return root

	if (root.val < key) {
		root.right = deleteNode(root.right, key)
	} else if (root.val > key) {
		root.left = deleteNode(root.left, key)
	} else {
		if (!root.left && !root.right) {
			root = null
		} else if (root.left) {
			const maxLeft = findMax(root.left)
			root.val = maxLeft.val
			root.left = deleteNode(root.left, maxLeft.val)
		} else {
			const minRight = findMin(root.right)
			root.val = minRight.val
			root.right = deleteNode(root.right, minRight.val)
		}
	}

	return root
}

function findMax(tree) {
	while (tree.right) {
		tree = tree.right
	}
	return tree
}

function findMin(tree) {
	while (tree.left) {
		tree = tree.left
	}
	return tree
}
